import java.util.LinkedList;
import java.util.Queue;

public class demo2 {
    //*
   static class Solution {
        int []dx={0,0,1,-1};
        int []dy={1,-1,0,0};
        boolean[][]ret;
        int m;
        int n;
        public void solve(char[][] board) {
            m=board.length;
            n=board[0].length;
            ret=new boolean[m][n];
            for(int i=0;i<m;i++){
                if(board[i][0]=='O'&&!ret[i][0])
                    dfs(board,i,0,'*');
                if(board[i][n-1]=='O'&&!ret[i][n-1])
                    dfs(board,i,n-1,'*');
            }
            for(int j=0;j<n;j++){
                if(board[0][j]=='O'&&!ret[0][j])
                    dfs(board,0,j,'*');
                if(board[m-1][j]=='O'&&!ret[m-1][j])
                    dfs(board,m-1,j,'*');
            }

            for (int i = 0; i <m ; i++) {
                for (int j = 0; j <n ; j++) {
                    if(i!=0&&i!=m-1&&j!=0&&j!=n-1){
                        if(board[i][j]=='O'&&!ret[i][j]){
                            dfs(board,i,j,'X');
                        }
                    }
                }
            }
            for(int i=0;i<m;i++){
                if(board[i][0]=='*'&&ret[i][0])
                    dfs1(board,i,0,'O');
                if(board[i][n-1]=='*'&&ret[i][n-1])
                    dfs1(board,i,n-1,'O');
            }
            for(int j=0;j<n;j++){
                if(board[0][j]=='*'&&ret[0][j])
                    dfs1(board,0,j,'O');
                if(board[m-1][j]=='*'&&ret[m-1][j])
                    dfs1(board,m-1,j,'O');
            }

        }
        public void dfs(char[][] board,int i,int j,char temp){
            Queue<int[]> queue=new LinkedList<>();
            queue.add(new int[]{i,j});
            while (!queue.isEmpty()){
                int[] arr = queue.poll();
                int a=arr[0];
                int b=arr[1];
                ret[a][b]=true;
                board[a][b]=temp;
                for(int k=0;k<4;k++){
                    int x=a+dx[k];
                    int y=b+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n&& !ret[x][y]&&board[x][y]=='O'){
                        ret[x][y]=true;
                        board[x][y]=temp;
                        queue.add(new int[]{x,y});
                    }
                }
            }
        }
        public void dfs1(char[][] board,int i,int j,char temp){
            Queue<int[]> queue=new LinkedList<>();
            queue.add(new int[]{i,j});
            while (!queue.isEmpty()){
                int[] arr = queue.poll();
                int a=arr[0];
                int b=arr[1];
                ret[a][b]=false;
                board[a][b]=temp;
                for(int k=0;k<4;k++){
                    int x=a+dx[k];
                    int y=b+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n&&ret[x][y]&&board[x][y]=='*'){
                        ret[x][y]=false;
                        board[x][y]=temp;
                        queue.add(new int[]{x,y});
                    }
                }
            }
        }

        public void solve1(char[][] board) {
            m=board.length;
            n=board[0].length;
            ret=new boolean[m][n];
            for(int i=0;i<m;i++){
                if(board[i][0]=='O'&&!ret[i][0])
                    dfs(board,i,0,'*');
                if(board[i][n-1]=='O'&&!ret[i][n-1])
                    dfs(board,i,n-1,'*');
            }
            for(int j=0;j<n;j++){
                if(board[0][j]=='O'&&!ret[0][j])
                    dfs(board,0,j,'*');
                if(board[m-1][j]=='O'&&!ret[m-1][j])
                    dfs(board,m-1,j,'*');
            }
            for(int i=0;i<m;i++){
                for (int j=0;j<n;j++){
                    if(board[i][j]=='O')board[i][j]='X';
                    if(board[i][j]=='*')board[i][j]='O';
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        char[][]borid={{'X','X','X','X'},
                {'X','O','O','X'},
                {'X','X','O','X'},
                {'X','O','X','X'}};
        solution.solve(borid);
    }
}
